Appendix C: Least Credits to cover all Group Specialist Missions

Glossary

Appendix C: Least Credits to cover all Group Specialist Missions

The most optimum way to upgrade ships to spend the least amount of credits, based on the current state of the upgrade levels of all your ships

With the list of all specialist missions and the corresponding ships that appear in all of Colonel , Major , Commander & Marshal , we can find the minimum number of ships to fully upgrade (to 6-6-6) to cover ALL group specialist missions for each rank.

• As this problem is NP-complete, the solution that presents the list of ships, even in Appendices B1, B2, B3 & B4, may only be an approximately optimal solution. These lists were generated based on the approaches presented in this Appendix C.
  • This problem can be modeled as a Weighted Set Covering Problem, which is a proven NP-complete problem. I will not bore you with the details of these 2 terms here.
  • If you are interested on what is a Set Covering Problem, navigate to the link of the website below. For the Numerical Example in the website below, replace Camera Location with the ships, and Stadium Areas with the different combinations of group specialist missions):
    https://optimization.cbe.cornell.edu/index.php?title=Set_covering_problem#Numerical_Example
    • Due to the different rarities of the ships (since you have to choose the minimum number of ships which are the sets in the problem) costing differently, as well as the different upgrade levels of your ships (which reduces the cost to fully upgrade them), the ships are "weighted".
    • In the Numerical Example of the website, there is no weight considered, meaning it is assumed all Cameras cost / weight the same. This example therefore models an Unweighted Set Covering Problem, which is an NP-hard problem.
  • You can search online on what is a Non-deterministic Polynomial-Time Complete (NP-complete) problem, if you are interested.
    • Be warned that this is a very difficult term to comprehend since it dives deep into the field of Computer Science and Mathematics.
    • Consider looking into the following types of problems: decision, optimization/search, Polynomial-Time (P), Non-deterministic Polynomial-Time (NP), NP-complete and NP-hard.
• If you didn't read that, or didn't understand anything, it doesn't matter. Just refer to the following appendices on the minimum number of ships to upgrade (and which ones to upgrade) for the different ranks:
  
  • Appendix B1 for Colonel
  • Appendix B2 for Major
  • Appendix B3 for Commander
  • Appendix B4 for Marshal
• If you upgrade these ships, it is guaranteed you can comfortably attempt all group specialist missions.
  • Note that there will be weapon affinity mismatches so you may not always be able to complete the specialist mission comfortably.
  • However, you could at least get a decent number of credits by bringing a well upgraded ship into the specialist mission.

However, the ships listed for upgrade to cover all group specialist missions may not be the most optimum solution for you, since you might have already upgraded some ships (either by spending credits or the Warp Gate doing it for you) which could be used as part of the ships to cover all group specialist missions.

• Note that for Marshal specialist missions, this approach will allow you to cover at least 60% of all specialist missions, since 50% of them are group specialist missions, while the other 50% are solo specialist missions.

The minimum number of ships to cover all group specialist missions is 19 for gold ranks and 20 for Marshal .

• For Marshal , this means covering at least 20% of all solo specialist missions, which equates to covering another at least 10% of all specialist missions.
• To cover ALL specialist missions in Marshal rank, it is necessary to own and upgrade every ship.

There are 2 approaches to this, so pick the one that is more ideal for you.

• As a fair warning, this process is quite involved and has a lot of technical steps.
• It may be easier to simply use the list of ships listed in Appendix B1, B2, B3 or B4 if you are not comfortable with some parts of the process detailed below.
• The solutions presented using either approach may only be approximately optimal solutions.
  
  • This is due to the nature of this Weighted Set Covering Problem being an NP-complete problem.
  • If you are interested, the approaches below use Randomized Rounding of Linear Programs (LPs) to derive the solutions.
    • The model used is either Google Linear Solver (Approach 1) or Simplex LP (Approach 2), which heavily implies the use of LPs.
    • The use of LPs is generally seen to be the preferred and more accurate approach for this problem rather than using a Greedy Algorithm (search it up if you are interested).

Approach 1 involves logging in to your Google Account while on the Google Sheet. You need to add the Google Sheet plugin OpenSolver to your Google Account. You can uninstall the OpenSolver plugin afterwards.

1. Go to:
   https://docs.google.com/spreadsheets/d/1Oebtve_fYCKZNCUjicbm5CjrE1gWfhaICngXzO_RmXU/
2. Login to your Google Account
3. Extensions > Add-ons > Get add-ons
4. Search for OpenSolver and install it
5. In the first sheet Player Ship Levels, enter in your ship upgrade levels.
   • If you have not unlocked the ship, enter 0 into Main Weapon or Aura.
   • If you do not want a specific ship to be considered for the pool of ships to upgrade, enter -1 into Main Weapon AND Aura.
   • If you are intending to obtain Phoenix by completing the Campaign (if you do not already have it and do not intend to buy it from the shop, thus obtaining it without credit costs), enter -1 into ALL of Main Weapon, Aura & Zen.
6. Change to 1 of the 4 sheets depending on your current rank, Min Ships to cover all Colonel/Major/Commander/Marshal Group Specs
7. Extensions > OpenSolver > Open sidebar
8. Use the following settings:
   1. Set the Objective Cell to $B$5
   2. Set the Objective Sense to minimise
   3. Set the Variable Cells to $B$4:$CS$4 by clicking on the Add button, and then click and drag the objective cells $B$4:$CS$4.
   4. Set the Constraint that cells $B$4:$CS$4 must be binary by highlighting on <Add new constraint>, type in $B$4:$CS$4, change the dropdown checkbox to bin, and click Save.
   5. Set the Constraint that $CT$8:$CT$107 >= $CV$8:$CV$107, by highlighting on <Add new constraint>, type in $CT$8:$CT$107 on the first text box, change the dropdown checkbox to >=, type in $CV$8:$CV$107 on the second text box, and click Save.
9. Click Solve Model and wait for the results.
10. Ships highlighted in green are the ships you should fully upgrade to cover all group specialist missions.
11. Consider repeating steps 1 - 10, but omit some ships highlighted in green in Step 10 from being considered for the pool of ships by entering -1 into Main Weapon AND Aura for these ships in Step 5.
    • Doing so allows you to explore several solutions.
    • You may even chance upon a more optimal solution since this problem is an NP-complete problem, as explained above.

Approach 2 involves downloading the Google Sheet as an Excel file and activating an already in-built (by default) Solver plugin for Excel. You can de-activate the Solver plugin afterwards.

You MUST use Microsoft Excel, no other spreadsheet software will work.

1. Go to:
   https://docs.google.com/spreadsheets/d/1Oebtve_fYCKZNCUjicbm5CjrE1gWfhaICngXzO_RmXU/
2. File > Download > Microsoft Excel (.xlsx)
3. Open up the Excel file you just downloaded with Microsoft Excel.
4. File > (Left Panel, bottom) Options > (Left Panel) Add-ins > (Bottom) Manage: Add-ins, click on Go.
5. Check the checkbox for Solver Add-in and click Ok.
6. In the first sheet Player Ship Levels, enter in your ship upgrade levels.
   • If you have not unlocked the ship, enter 0 into Main Weapon or Aura.
   • If you do not want a specific ship to be considered for the pool of ships to upgrade, enter -1 into Main Weapon AND Aura.
7. Change to 1 of the 4 sheets depending on your current rank, Min Ships to cover all Colonel/Major/Commander/Marshal. (Sorry, Excel cuts off the rest of the words due to a character limit on sheet names)
8. Data > Analyze > Solver
9. Use the following settings for the Solver Parameters:
   1. Set Objective: $B$5
   2. To: Min
   3. By changing Variable Cells: $B$4:$CS$4
   4. Click on Add, Cell Reference: $B$4:$CS$4. Change the dropdown box to bin. Click Add.
   5. Cell Reference: $CT$8:$CT$107. Change the dropdown box to >=. Constraint: $CV$8:$CV$107. Click Add.
   6. Click on Cancel
10. Select a Solving Method: Simplex LP
11. Click Solve and wait for the results.
12. Ships highlighted in green are the ships you should fully upgrade to cover all group spec missions.
13. Consider repeating steps 1 - 12, but omit some ships highlighted in green in Step 12 from being considered for the pool of ships by entering -1 into Main Weapon AND Aura for these ships in Step 6.
    • Doing so allows you to explore several solutions.
    • You may even chance upon a more optimal solution since this problem is an NP-complete problem, as explained above.